The present invention relates in general to image processing and in particular to a method for determining a displacement vector in an image processing operation.
In image processing, displacement vectors or motion vectors function by a known approach to define a change in position of an object or image area from a first position within a first image to a second position within a second image.
The two images can be recorded temporally sequentially, thereby graphically representing a movement of the object or image area in a displayed image segment over time. In such cases, the motion vector serves, for example, to interpolate one or more intermediate images which reproduce the position of the object at one or more instants in time between the recording of the first and second images, for example, in the case of 50 Hz/100 Hz video conversion or when generating “artificial time expansions.”
The two images can also be recorded simultaneously from first and second camera positions, where the displacement vector to be determined serves to generate an intermediate image which shows the object from another virtual cameral position which is located at a position different from the first and second camera positions.
FIG. 1 illustrates two images B1, B2, which may have been recorded in temporal succession or from different camera positions, having a first image area 1 at a first position P1 within the first image B1, and a second image area 2 at a second position P2 within the second image B2. For simplicity, the first and second image areas 1, 2 are represented as squares, the midpoints of which are identified by the positions P1, P2 within the image areas. The image areas may have any desired shape.
As FIG. 1 illustrates, the second image area 2 in the second image B2 results from a displacement of the first image area 1 of the first image B1 by a displacement vector vec. This displacement can be a function of time when the two images B1, B2 are recorded in succession and an object representing the first image area 1 moves within the examined image segment from the position P1 at the instant the first image B1 is recorded to the position 2 at the instant the second image B2 is recorded. This displacement of the two image areas 1, 2 within the displayed image segment can also be the result of the fact that the two images B1, B2 are recorded at the same instant but from different viewing angles.
One basic approach, known for determining this type of displacement vector for a given image area or object, is to divide the image into individual image areas and supply test vectors, each of which represents a possible displacement vector for the individual image areas. Using these test vectors, image comparisons are performed by which image information, for example, luminance values or chrominance values for the individual pixels of an examined image area in the first image, is compared with image information values for a second image area in the second image, where one selection vector each is used to displace the position of the second image area in the second image relative to the position of the first image area in the first image. Out of the various test vectors, the one or more selection vectors are chosen which provide the “best” comparison result, for which the best match is determined between the first and second image areas.
The quality of this method is a function of the selection vectors chosen since it is difficult from a practical view to perform an image comparison for all of the possible displacement vectors due to the need to keep the already high computational effort within certain limits. It is thus a fundamental goal of these methods to reduce the number of required image comparisons without accepting degradation of the result in the determination of the at least one selection vector.
A known method for reducing the effort/complexity is to utilize certain prior information in the selection of test vectors for a given image area, which information has been obtained, for example, in previous search steps for the given image area, or in search steps for an adjacent image area. This prior information results in a group of prediction vectors from which the test vectors are generated or selected. These prediction vectors, which were obtained using search steps for adjacent image areas or using previous search steps for the image areas examined, can be accepted as the test vector for the area of interest, and/or the test vectors can be generated from these prediction vectors by changing their length and/or direction according to a predetermined or random scheme, whereby in this last-named case the prediction vectors can change from search step to search step.
The selection vectors determined from the test vectors can be utilized as new prediction vectors during the subsequent search steps.
To illustrate this method, FIG. 2 provides a schematic view of a known vector search system which determines displacement vectors for individual image areas and which incorporates prediction vectors to determine a possible displacement vector, the prediction vectors containing results from previous search steps for the same image area, or results from search steps for adjacent image areas. The system comprises a test vector determination unit 10 to which a set of prediction vectors are supplied and which provides a set of test vectors from these prediction vectors. The provision of test vectors can be implemented by passing on unchanged some or all of the prediction vectors as test vectors. In addition, it is possible to modify some or all the prediction vectors according to a fixed or random scheme to generate the test vectors.
The test vectors are employed in an image comparison unit 20, connected to the output of the test vector determination unit 10, to perform image comparisons for the individual image areas, where, with reference to FIG. 1, one image area 1 from the first image B1 is always compared with an image area 2 from the second image B2, while from the second image B2 for each comparison that second image area is selected, the geometry of which matches the geometry of the first image area 1 and which area is displaced relative to the first image area 1 of the first image 1 by one of the selection vectors.
The results determined for the individual comparisons are supplied to a selection unit 30 which, based on the comparison results, selects at least one selection vector for which the best comparison result was determined out of the group of test vectors. The at least one vector selected based on the comparison results represents the actual displacement vector, or at least the most likely displacement vector, which maps the first image area 1 from the first image B1 onto the second image area 2 in the second image B2. In the determination of the comparison result, it is possible to evaluate the test vectors differently as a function of how they were generated. For example, it is possible in the image comparison to “penalize” the prediction vectors or test vectors determined based on the image comparisons for previous images, that is, to grade them lower than test vectors that were determined for adjacent image areas within the same image.
In this known method, the selection vectors are always a function of the prediction vectors. However, an appropriate utilization of these prediction vectors requires that the displacement of adjacent image areas, or the displacement of the image area of interest, does not undergo significant variations over time, since it must be ensured that the selection vectors determined from the prediction vectors also contain the actual displacement vector. Otherwise a considerable expansion in the number of selection vectors is required.
What is needed is an improved method for determining in image processing at least one selection vector which is in particular capable of taking into account rapid changes in the displacement vectors.